package com.shixianchen.study.day6;

import com.shixianjun.sort.Sortable;
import com.shixianjun.sort.SortableElement;

/**
 * @author ShiXianChen
 * @version V1.0.0
 * @Description 归并排序
 * @date 2022/11/9 22:51
 */
public class MergeSort implements Sortable {
    @Override
    public void sort(SortableElement[] arr) {
        sortMarge(arr, 0, arr.length - 1);
    }

    public void sortMarge(SortableElement[] arr, int left, int right) {
        //当只有一个元素的时候
        if (left == right) {
            return;
        }
        //分成两半
        int mid = left + (right - left) / 2;
        //左半部分排序
        sortMarge(arr, left, mid);
        //右半部分排序
        sortMarge(arr, mid + 1, right);
        //进行归并
        merge(arr, left, mid + 1, right);
    }


    private void merge(SortableElement[] arr, int leftPtr, int rightPtr, int rightBound) {
        //创建边界
        int mid = rightPtr - 1;
        //创建数组
        SortableElement[] temp = new SortableElement[rightBound - leftPtr + 1];

        //左起始点
        int i = leftPtr;
        //有起始点
        int j = rightPtr;
        //新的数组起始下标
        int k = 0;

        while (i <= mid && j <= rightBound) {
            if (arr[i].value <= arr[j].value) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }

        while (i <= mid) {
            temp[k++] = arr[i++];
        }

        while (j <= rightBound) {
            temp[k++] = arr[j++];
        }

        for (int m = 0; m < temp.length; m++) {
            arr[leftPtr+m] = temp[m];
        }
    }


}
